#ifndef QUICK_SORT_H
#define QUICK_SORT_H

#include <string.h>
using namespace std;

template <class T>
void swap(T *a, int i, int j)
{
    T temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

template <class T>
T choose_pivot(T *a, int left, int right)
{
    return a[left];
}

template <class T>
int partition(T *a, int left, int right, T pivot, int nSize)
{
    int i,j;
    for (i=left,j=right; i<=j; )
    {
    	for ( ; memcmp(a[i],pivot, nSize) < 0 ; ++i)
    		;
 	    for ( ; memcmp(a[j],pivot,nSize) > 0; --j)
   	        ;
        if (i<=j)
        {
            swap(a,i,j);
            ++i;
            --j;
        }
    }
    return i;
}




template <class T>
void quick_sort(T *a, int left, int right, int nSize)
{
    int i;
    T pivot;

    if (left>=right)
        return;

    pivot = choose_pivot(a,left,right);
    i = partition(a,left,right,pivot,nSize);

    quick_sort(a,left,i-1,nSize);

    quick_sort(a,i,right,nSize);
}

#endif
